package com.sunny.l21;

import java.util.concurrent.LinkedBlockingQueue;

public class Solution {

    private static final int[][] direct = {{0,1},{0,-1},{1,0},{-1,0}};

    LinkedBlockingQueue<Point> queue = new LinkedBlockingQueue<>();

    public static void main(String[] args) {
//        char[][] board = {{'X','O','O'}};
//        char[][] board = {{'X','X','X','X'},{'X','O','O','X'},{'X','X','X','X'},{'X','O','O','X'}};
//        char[][] board = {{'X','O','X','X'}};
//        char[][] board = {{'X'},{'O'},{'X'},{'X'}};
        char[][] board = {{'O','X','X'},{'X','O','X'},{'X','X','X'}};
        Solution solution = new Solution();
        solution.solve(board);
        solution.print(board);
    }

    public void solve(char[][] board) {

        if(board == null)
            return;

        int n = board.length;
        if(0 == n)
            return;
        int m = board[0].length;
        boolean[][] fix = new boolean[n][m];

        //查找四个边界
        for(int i = 0; i < m; i++ ){
            if(!fix[0][i] && 'O' == board[0][i]){
                bfs(board, fix, 0, i, n, m);
//                dfs(board, fix, 0, i, n, m);
            }
            if(!fix[n-1][i] && 'O' == board[n-1][i]){
                bfs(board, fix, n-1, i, n, m);
//                dfs(board, fix, n-1, i, n, m);
            }
        }
        for(int i = 0; i < n; i++){
            if(!fix[i][0] && 'O' == board[i][0]){
                bfs(board, fix, i, 0, n, m);
//                dfs(board, fix, i, 0, n, m);
            }
            if(!fix[i][m-1] && 'O' == board[i][m-1]){
                bfs(board, fix, i, m-1, n, m);
//                dfs(board, fix, i, m-1, n, m);
            }
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if('O' == board[i][j] && !fix[i][j]){
                    board[i][j] = 'X';
                }
            }
        }
//        print(fix);

    }

    public void dfs(char[][] board, boolean[][] fix, int iInd, int jInd, int n, int m){
        fix[iInd][jInd] = true;
        for(int i=0;i<4;i++){
            Point newP = new Point(iInd+direct[i][0], jInd+direct[i][1]);
            if(newP.judge(n, m) && !fix[newP.x][newP.y] && 'O' == board[newP.x][newP.y]){
                dfs(board, fix, newP.x, newP.y, n, m);
            }
        }
    }

    public void bfs(char[][] board, boolean[][] fix, int iInd, int jInd, int n, int m){
        queue.clear();
        Point start = new Point(iInd, jInd);
        queue.offer(start);
        while (!queue.isEmpty()){
            Point tmp = queue.poll();
            fix[tmp.x][tmp.y] = true;
            for(int i=0;i<4;i++){
                Point newP = new Point(tmp.x+direct[i][0], tmp.y+direct[i][1]);
                if(newP.judge(n, m) && !fix[newP.x][newP.y] && 'O' == board[newP.x][newP.y]){
                    queue.offer(newP);
                }
            }
        }
    }

    public void print(char[][] board){
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[i].length;j++){
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }

    public void print(boolean[][] fix){
        for(int i=0;i<fix.length;i++){
            for(int j=0;j<fix[i].length;j++){
                System.out.print(fix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

class Point{
    int x,y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public boolean judge(int n, int m){
        if(this.x < 0 || this.x >= n || this.y < 0 || this.y >= m)
            return  false;
        return true;
    }
}